package 每日一题OJ;

/**
 * @author shy_black
 * @date 2019/3/18 21:42
 * @Description:
 */
public class 连续子数组的最大和 {
    //暴力枚举法
    public int FindGreatestSumOfSubArray(int[] arr) {
        int cursum = 0;
        int max = arr[0];
        for(int i = 0;i < arr.length;i++) {
            for(int j = i ;j < arr.length;j++) {
                cursum = 0;
                for(int k = i;k < arr.length;k++) {
                    cursum += arr[k];
                    if(cursum > max) {
                        max = cursum;
                    }
                }
            }
        }
        return max;
    }
    public static int MaxAddSub(int[] arr,int from,int to) {
        if(to == from) {
            return arr[from];
        }
        int mid = (from + to) / 2;
        int m1 = MaxAddSub(arr,from,mid);
        int m2 = MaxAddSub(arr,mid+1,to);
        int i ,left = arr[mid],cur = arr[mid];
        for(i = mid -1;i >= from;--i) {
            cur += arr[i];
            left = cur > left ? cur:left;
        }
        int right = arr[mid+1];
        for(i = mid + 2;i <= to; i++) {
            cur += arr[i];
            right = cur > right ? cur : right;
        }
        int m3 = left + right;
        int temp = m1>m2 ? m1:m2;
        return temp > m3 ? temp : m3;

    }
    //连续子数组的最大和------>动态规划
    public int FindGreatestSumOfSubArray_1(int[] arr) {
        int result = arr[0];
        int sum = 0;
        for(int i = 0;i < arr.length;i++) {
            if(sum > 0)
                sum += arr[i];
            else
                sum = arr[i];
            if(sum > result)
                result = sum;
        }
        return result;
    }

}